/*
    http://bhepple.freeshell.org

    Copyright (C) 2010 Bob Hepple <bhepple@freeshell.org>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING.  If not, write to
    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

*/

/**
 * \file tba.h - Safe dynamic array package. 
 * 
 * Expands arrays if necessary so that most things just work without
 * fussing about 'is it long enough', 'am I passing in a NULL
 * reference' etc. It's actually an array of pointers terminated with
 * a NULL, each pointing to an item or 'payload' defined by the caller
 *
 * Simplest case is to use:

tba a = NULL;
tba_push_str(&a, string1); 
tba_push_str(&a, string2);
// 'a' is now an argv-like array including a NULL terminator
...
for (i = 0; a[i]; i++) xfree(a[i]);
tba_free(&a);

 * If the array is created (by tba_new()) with a positive
 * 'payload_size' then the package takes care of alloc'ing and
 * free'ing the payloads. Otherwise (ie payload_size == 0) it's up to
 * the caller to do it. In either case, callbacks are available so
 * that the creation of the payloads can be customised. Arrays with
 * payload_size or callbacks set are termed 'managed arrays' as the
 * package automatically creates items as needed.
 *
 * eg here's a simple case where all payloads are the same and tba
 * is allowed to do all the alloc'ing and free'ing (payload_size > 0):

\verbatim
 typedef struct {
     int count;
     char description[50];
 } my_payload *t;
 
 // alloc space for 500 my_payloads:
 tba a = tba_new(500, sizeof(my_payload), NULL, NULL, NULL, NULL); 
 // a[0..499] are alloc'd; a[500] == NULL
 for (i = 0; a[i]; i++) {
     t = (my_payload *)a[i];
     t->count = i;
     snprintf(t->description, 50, "this is payload %d", i);
 }
 t = (my_payload *)a[234];
 printf("%d: desc=%s\n", t->count, t->description); // gives:
 //234: desc=this is payload 234
 tba_free(a); // all gone
 \endverbatim

 * NB more simple examples in the tests directory
 * 
 * This library doesn't leak memory itself (according to valgrind
 * running on Linux) so you can make a caller watertight by using
 * tba_free() appropriately - and by freeing anything pointed to
 * by array members before deleting them! The free_callback is
 * provided to make this simple.
 *
 * In all the routines, if a (tba *) argument is required, then it
 * means the argument may need to be re-sized. In all cases, if there
 * is an error then the original value will _not_ be modified.
 *
 * These routines call xcalloc, xrealloc, xfree which must be provided
 * by the caller. This provides an opportunity to handle out-of-memory
 * conditions as desired. For example, you might call calloc(1, 64000)
 * on the first call to xcalloc - then, if you run out, you could free
 * the safety buffer and longjmp out to a handler to do an emergency
 * stop or other recovery. Note: xrealloc should call xmalloc if
 * handed a NULL pointer - as on GNU libc. There's a simple
 * implementation of xmalloc etc in the unit test
 * tests/tba_test.c. Note that the usual implementation of xmalloc
 * etc is to never return a NULL pointer eg on out-of-memory. tba
 * does not make that assumption and allows you to let xmalloc()
 * return a NULL just like malloc().
 *
 * tbas are thread safe provided the usual rules for using objects
 * in threads are applied by the caller - ie lock around write-access
 * to shared arrays or array payloads. The only proviso is that if
 * tba_set_chunksize is called, it should be called before
 * threads start. Otherwise, if called in a thread, the only confusion
 * is that threads might fight over the optimum chunksize to use.
 *
 */

#ifndef _XMALLOC_H
void *xcalloc(size_t nmemb, size_t size);
void *xmalloc(size_t size);
void xfree(void *ptr);
void *xrealloc(void *ptr, size_t size);
#endif /* _XMALLOC_H */

/**
 * A safe array object
 */
typedef void **tba;

/**
 * Add a string to an array.
 * \param dest [IN/OUT] the destination array; if NULL, one will be created.
 * \param string [IN] a string to add - the new entry in the array will be malloc'ed and copied
 * \return NULL on error
 */
tba tba_push_str(tba * dest, const char * string);

/**
 * Free a payload - will be called when a payload must be free'd. It
 * will be passed a pointer to the payload which is about to be freed
 * - this is the last chance to use or free anything in there. The
 * alternative is to do the payload free'ing before the tba_free
 * call is made, just make sure all the array pointers are set to
 * NULL.
 *
 * \param payload [IN] payload which is about to be freed. 
 *
 * \param index [IN] index of the payload being freed
 *
 * \param caller_data [IN] pointer to the caller data provided in the
 * call to tba_new.
 *
 * \return NULL if the callback free'd the payload, else return
 * payload. It's most important to get this right!!! Take care.
 */
typedef void *(*tba_free_callback_t)(void *payload, size_t index, 
                                         void *caller_data);

/**
 * Create a new payload - this is called when a new payload needs to
 * be created. It provides an opportunity for the caller to fill out
 * values in the payload. The alternative is to do the payload
 * creations after the tba is created.
 *
 * If a fixed size payload is defined (ie payload_size was provided in
 * the original tba_new call) the space for the payload will
 * already have been created for you by the package. Otherwise you
 * _must_ alloc the payload in this callback and provide its address
 * in the return value.
 *
 * \param payload [IN] a pointer to the payload storage if it was
 * alloc'd by tba (ie payload_size is known) otherwise NULL.
 *
 * \param index [IN] the index of the payload being created.
 *
 * \param caller_data [IN] pointer to the caller data provided in the
 * call to tba_new.
 *
 * \return the callback should return the address of the payload. If
 * the callback encountered a problem (eg an out of memory condition)
 * it should return NULL. In this (error recovery) case tba_new
 * will free up anything already created (possibly calling the
 * tba_free_payload_t callback) and return NULL.
 */
typedef void *(*tba_create_callback_t)(void *payload, size_t index, 
                                       void *caller_data);

/**
 * Copy a payload - this is called when a payload needs to be copied.
 * It provides an opportunity for the caller to supply values in the
 * new payload. The alternative is to do the copying after the tba
 * is created. This callback may call the create_callback to get a new
 * item. As with create_callback, if the payload_size > 0 then a
 * zero'd memory block will have been created for you in dest_payload.
 *
 * \param dest_payload [IN] a pointer to the destination payload
 * storage if it was already alloc'd by tba (ie payload_size is
 * known) otherwise NULL in which case the callback _must_ alloc the
 * payload and provide its address in the return value.
 *
 * \param source_payload [IN] a pointer to the source payload
 *
 * \param index [IN] the index of the payload being created.
 *
 * \param caller_data [IN] pointer to the caller data provided in the
 * call to tba_new.
 *
 * \return the callback should return the address of the payload. If
 * the callback encountered a problem (eg an out of memory condition)
 * it should return NULL. In this (error recovery) case tba_new
 * will free up anything already created (possibly calling the
 * tba_free_payload_t callback) and return NULL.
 */
typedef void *(*tba_copy_callback_t)(void *dest_payload, 
                                     void *source_payload,
                                     size_t index, 
                                     void *caller_data);

/**
 * Set the quantum of allocation (initially 1) for tbas created
 * from now on. tbas will be calloc'd to a multiple of this value
 * (rounded up to a multiple of sizeof(void *)).
 *
 * \param chunksize [IN] in bytes > 0
 */
void tba_set_chunksize(size_t chunksize);

/**
 * Create a new tba to contain num items (payloads). If
 * payload_size or callbacks are set then the array is managed by the
 * package (as described above). If one callback is set then they must
 * all be set.
 *
 * \param num [IN] initial number of payloads
 *
 * \param payload_size [IN] the size of each payload - if set > 0 then
 * tba will create and destroy them as needed. Set payload_size to
 * 0 to do your own memory management - for example, if the payloads
 * are of varying size. In this case the array will be initially
 * filled with NULLs. The array will be terminated with an additional
 * NULL member.
 * 
 * \param free_callback [IN] if non-NULL, this is called when a
 * payload needs to be free'd. It provides an opportunity for the
 * caller to free anything pointed to in the payload.
 * 
 * \param create_callback [IN] if non_NULL, this is called when a
 * payload need to be created. It provides an opportunity for the
 * caller to fill out the payload structure.
 *
 * \param copy_callback [IN] if non-NULL, this is when a payload needs
 * to be copied. It provides an opportunity for the caller to copy
 * anything pointed to in the payload.
 *
 * \param caller_data [IN] pointer to the caller's data which will be
 * passwd to the callbacks. If not needed, then set to NULL. Note that
 * if it is given then the data must be viable for as long as the
 * returned tba is in use otherwise corruptions may occur.
 *
 * \return new tba or NULL on error
 */
tba tba_new(size_t                num, 
            size_t                payload_size,
            tba_free_callback_t   free_callback,
            tba_create_callback_t create_callback,
            tba_copy_callback_t   copy_callback,
            void *                caller_data);

/**
 * Free a tba object
 *
 * \param s [IN] object to free
 */
void tba_free(tba *s);

/**
 * Fetch the num'th item from the array. Could also be done more
 * efficiently by source[num] but without the range checking.
 *
 * \param source [IN] array
 *
 * \param num [IN] index into the array
 *
 * \returns the value of the num'th element or NULL on error (or if
 * the value is NULL!)
 */
void *tba_get_index(const  tba source, size_t num);

/**
 * Set the num'th item from the array. Could also be done with less
 * overhead by 'dest[num] = value' - but without the range checking.
 *
 * Also, note that if tba_put_index() is used, the array can keep track
 * of the highest address used and later on use it as the length
 * returned by tba_get_len(). Otherwise (ie if 'dest[i] =
 * something;' is used) then tba_get_len() works back from the end
 * of the array till it finds a non-NULL item. You should probably not
 * mix tba_put_index() and dest[i]=something unless you know what you
 * are doing.
 *
 * Notes on managed arrays:
 *
 * If tba_put_index() is used on a managed array (ie one with non-zero
 * payload_size or callbacks) then make sure you only _put items that
 * the array package will be able to free() when the time comes. In
 * other words, if payload_size is set, then only _put items created
 * with malloc() and if free_callback is set, then only _put items
 * that can be sent to the callback.
 *
 * If you do a _put of a non-NULL item beyond the last item of a
 * managed array, then the intervening items will be automatically
 * created for you.
 *
 * \param dest [IN/OUT] array
 *
 * \param num [IN] index into the array
 *
 * \param value [IN] value to assign to dest[num] - if payload_size >
 * 0 or callbacks are set for this array, this must be a pointer to a
 * suitably malloc'd block. If payload_size and callbacks are unset
 * (ie an unmanaged array) then this can be anything you want.
 *
 * \returns NULL on error; else dest
 */
tba tba_put_index(tba *dest, size_t num, void *value);

/**
 * Return the maximum length of a tba
 *
 * \param s [IN] tba
 *
 * \return int maximum length or 0
 */
int tba_get_maxlen(tba  s);

/**
 * Return the length of a tba - if tba_put_index() has been used
 * then it returns the largest known item. Otherwise, it works back
 * from the end of the array to find the last non-NULL item.
 *
 * \param s [IN] tba
 *
 * \return int length or -1 on error
 */
int tba_get_len(tba  s);

/**
 * Resize a tba - resize an array - you will lose elements if you
 * truncate it!
 *
 * \param dest [IN/OUT] tba to modify (can be NULL and a new one
 * will be created)
 *
 * \param newlen [IN] new maxlen for dest
 *
 * \return dest or NULL on error (*dest is unchanged on error)
 */
tba tba_resize(tba *dest, size_t newlen);

/**
 * Insert a number of items into a tba. If the payloads are
 * 'managed' then the new items are created. The create_callback, if
 * defined, is called so you have a chance to populate the item.
 *
 * \param dest [IN/OUT] tba to be modified - may be expanded
 *
 * \param pos [IN] position to insert (zero-based, -1 inserts at the end)
 *
 * \param num [IN] number to insert
 *
 * \return new value of dest or NULL on error (*dest is unchanged on error)
 */
tba tba_insert(tba *dest, size_t pos, size_t num);

/**
 * Delete a number of items from a tba
 *
 * \param dest [IN] tba to be modified
 *
 * \param pos [IN] position to delete (zero-based, -1 deletes at the end)
 *
 * \param num [IN] number to delete
 *
 * \return new value of dest or NULL on error
 */
tba tba_delete(tba dest, size_t pos, size_t num);

/**
 * Create a new tba as a copy of an existing one. If the array is
 * managed then payloads are automatically created for the
 * destination and the copy_callback is called (if defined) so you
 * have an opportunity to populate them. The physical size of the new
 * array is minimised - so this is one way to shrink existing large
 * arrays (apart from tba_resize).
 *
 * \param source [IN] source tba 
 *
 * \return new tba copied from source
 */
tba tba_copy(const tba source);

/**
 * Copy an array to the end of another. Both arrays must have
 * identical payload_size properties. The copy_callback of dest will
 * be called if present. If *dest is NULL then this is equivalent to
 * tba_copy()
 *
 * \param dest [IN/OUT] destination array (may point to NULL and it
 * will be created). dest will be expanded if necessary.
 *
 * \param source [IN] source array to append to dest
 *
 * \return new value of dest or NULL on error (*dest is unchanged on error)
 */
tba tba_cat(tba *dest, tba source);

/**
 * Push a new item onto a queue/stack FIFO/LIFO (implemented with a
 * tba). (this is the same as tba_insert(stack, -1))
 *
 * Notes on managed arrays:
 *
 * If tba_push() is used on a managed array (ie one with non-zero
 * payload_size or callbacks) then make sure you only _push items that
 * the array package will be able to free() when the time comes. In
 * other words, if payload_size is set, then only _push items created
 * with malloc() and if free_callback is set, then only _push items
 * that can be sent to the callback.
 *
 * \param stack [IN] tba - may be NULL and a new one will be
 * created (with zero payload_size and no callbacks).
 *
 * \param item [IN] item to store on the stack
 *
 * \return new tba copied from source or NULL on error
 *
 */
tba tba_push(tba *stack, void *item);

/**
 * Get the newest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tba
 *
 * \return NULL on error, else stack
 *
 */
void *tba_get_last(const tba stack);

/**
 * Get the oldest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tba
 *
 * \return NULL on error, else stack
 *
 */
void *tba_get_first(const tba stack);

/**
 * Pop the newest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tba
 *
 * \return most recently pushed item in the array, or NULL on error.
 *
 */
void *tba_pop_last(tba stack);

/**
 * Pop the oldest item from a queue/stack FIFO/LIFO
 *
 * \param stack [IN] tba
 *
 * \return least recently pushed item in the array, or NULL on error.
 *
 */
void *tba_pop_first(tba stack);

